package dfs_bfs.test52;

/**
 * N皇后问题
 * @author code_yc
 * @version 1.0
 * @date 2020/7/9 11:09
 */
public class Solution1 {

    boolean[] col;
    boolean[] d;
    boolean[] ud;
    int ans = 0;

    public int totalNQueens(int n) {
        col = new boolean[n];
        d = new boolean[2 * n];  // 反对角线 ： 行 + 列 的值相等
        ud = new boolean[2 * n];  // 正对角线：  行 - 列  + n 的值相等，同增同减

        dfs(0, n);
        return ans;
    }

    private void dfs(int c, int n) {
        if (c == n) {
            ans++;
            return;
        }
        // 枚举每一列
        for (int i = 0; i < n; i++) {
            if (!col[i] && !d[c + i] && !ud[c - i + n]) {
                col[i] = d[c + i] = ud[c - i + n] = true;
                dfs(c + 1, n);
                col[i] = d[c + i] = ud[c - i + n] = false;
            }
        }
    }
}
